package nc.jv.Sort;

/**
 * @author Vadim Gidulyan
 *
 */
public class MergeSorter implements Sorter
{

	@SuppressWarnings("rawtypes")
	@Override
	public void sort(Comparable[] array)
	{
		if (array == null)
			throw new NullPointerException();
		if (array.length-1 <= 0)
			return;
		
		Comparable[] sa = array; // sorted array
        array = array.clone();   // unsorted/temporary array            
        
        int pow2length = minPowOfTwo(array.length);

        Comparable[][] c = new Comparable[][] {array, sa};
        if (log2(pow2length) % 2 == 0) // if length == 4, 16, 64 etc.
                xchg(c);
        
        for (int p = 1; 2*p <= pow2length; p *= 2) // while p less than half
        {
                for (int i = 0; i < array.length; i += 2*p)
                        merge(c[0], c[1], i, p);
                xchg(c);
        }
	}
	
	/**
     * Вспомогательный метод для сортировки массива
     * 
     * <p> В массиве {@code unsortedArray} выделяется блок с позиции {@code startIndex} размером {@code p}.
     * За ним выделяется второй блок размером {@code p}. Оба блока сливаются попеременным шаганием по блокам
     * в массив {@code sortedArray} начиная с позиции {@code startIndex}. Когда один из блоков заканчивается,
     * все оставшиеся элементы второго блока добавляются в резельтирующий массив {@code sortedArray}
     * 
     * @param unsortedArray
     *                Массив, который нужно отсортировать
     * 
     * @param sortedArray
     *                Массив, в который будет передан отсортированный массив {@code unsortedArray}
     * 
     * @param startIndex
     *                Начало блока для сортировки
     * 
     * @param p
     *                Размер блока сортировки
     */
    @SuppressWarnings({ "rawtypes", "unchecked" })
    private static void merge(Comparable[] unsortedArray,
                                                      Comparable[] sortedArray,
                                                      final int startIndex,
                                                      int p)
    {
            int leftIndex  = startIndex,
                    rightIndex = startIndex + p,
                    outIndex   = startIndex;
            final int leftEnd  = (startIndex + p) <= unsortedArray.length
                                                     ? startIndex + p
                                                     : unsortedArray.length,
                              rightEnd = (startIndex + 2*p) <= unsortedArray.length
                                                     ? startIndex + 2*p 
                                                     : unsortedArray.length;

            while (leftIndex < leftEnd && rightIndex < rightEnd)
                    if (unsortedArray[leftIndex].compareTo(unsortedArray[rightIndex]) < 0) // sort by ascending
                            sortedArray[outIndex++] = unsortedArray[leftIndex++];
                    else
                            sortedArray[outIndex++] = unsortedArray[rightIndex++];
            
            while (leftIndex < leftEnd)
                    sortedArray[outIndex++] = unsortedArray[leftIndex++];
            
            while (rightIndex < rightEnd)
                    sortedArray[outIndex++] = unsortedArray[rightIndex++];                  
    }
    
    /**
     * Меняет местами первые два элемента в массиве
     * 
     * <p> Необходимо для {@link #sort(Comparable[])}
     * 
     * @param array
     *                Любой массив объектного типа
     */
    private static void xchg(Object[] array)
    {
            Object temp = array[0];
            array[0] = array[1];
            array[1] = temp;
    }
    
    /**
     * Определяет минимальную степень числа 2, большую заданного
     * 
     * <p>
     * <code> minPowOfTwo(4) </code> вернет 4
     * <p>
     * <code> minPowOfTwo(5) </code> вернет 8
     * 
     * @param number
     *                Заданное число
     * 
     * @return Степень числа 2, большую заданного числа {@code number}
     */
    private static int minPowOfTwo(int number)
    {
            return isPowerOfTwo(number)
                       ? number                                                       // 4 -> 4
                       : 2*Integer.highestOneBit(number); // 5 -> 8
    }
    
    /**
     * Определяет является ли число степенью 2
     * 
     * @param number
     *                Число
     * 
     * @return
     *                 <ul><li>{@code true} если число является степенью 2
     *                         <li>{@code false} если число не является степенью 2</ul>
     */
    private static boolean isPowerOfTwo(int number) 
    {
            return (number & -number) == number;
    }
    
    /**
     * Определяет логарифм числа по основанию 2
     * 
     * @param number
     *                Число, логарифм которого нужно найти
     * 
     * @return
     *                 Логарифм числа {@code number} по основанию 2
     */
    private static int log2(int number)
    {
            return Integer.SIZE - 1 - Integer.numberOfLeadingZeros(number);
    }
    
}
